struct DifTree {
    int root;
    int n, M;
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> parent;
    std::vector<int> dep;
    std::vector<int> diff;
    std::vector<int> sz;
    
    DifTree(int n, int root = 0) : n(n), adj(n), dep(n), diff(n), root(root), sz(n) {
        // M = (sizeof(n) * 8) - std::countl_zero(n) - 1;
        M = (sizeof(n) * 8) - __builtin_ctz(n) - 1;
        parent.assign(n, std::vector<int>(M, -1));
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void dfs(int u, int f) {
        if (f != -1) {
            dep[u] = dep[f] + 1;
        }
        parent[u][0] = f;
        for (int i = 1; i < M && parent[u][i - 1] != -1; ++i) {
            parent[u][i] = parent[parent[u][i - 1]][i - 1];
        }
        sz[u] = 1;
        for (auto v : adj[u]) {
            if (v == f) {
                continue;
            }
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
    
    void setup(int u) {
        dfs(u, -1);
    }
    
    void setup() {
        setup(root);
    }
    
    int lca(int u, int v) {
        if (dep[u] < dep[v]) {
            std::swap(u, v);
        }
        for (int i = dep[u] - dep[v]; i != 0; i &= i - 1) {
            u = parent[u][__builtin_ctz(i)];
        }
        // for (int i = M - 1; i >= 0; --i) {
        //     if (parent[u][i] != -1 && dep[parent[u][i]] >= dep[v]) {
        //         u = parent[u][i];
        //     }
        // }
        if (u == v) {
            return u;
        }
        for (int i = M - 1; i >= 0; --i) {
            if (parent[u][i] != -1 && parent[u][i] != parent[v][i]) {
                u = parent[u][i], v = parent[v][i];
            }
        }
        return parent[u][0];
    }
    
    void add(int u, int v, int x) {
            int p = lca(u, v);
        diff[u] += x, diff[v] += x, diff[p] -= x;
        int q = parent[p][0];
        if (q != -1) {
            diff[q] -= x;
        }
    }
    
    void work(int u, int f) {
        for (auto v : adj[u]) {
            if (v == f) {
                continue;
            }
            work(v, u);
            // do something
            // if (diff[v] == 0) {
            //     ans += m;
            // } else if (diff[v] == 1) {
            //     ++ans;
            // }
            diff[u] += diff[v];
        }
    }
    
    void work() {
        work(root, -1);
    }

    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    bool line(int x, int y, int z) {
        int v = lca(x, z);
        // return (lca(x, y) == y || lca(y, z) == y) && lca(v, z) == v;
        return dist(x, z) == dist(x, y) + dist(y, z);
    }

    int intree(int x, int y) { // x 在 y 的子树大小
        if (x == y) {
            return 0;
        }
        for (int i = M - 1; i >= 0; --i) {
            if (parent[x][i] != -1 && dep[parent[x][i]] > dep[y]) {
                x = parent[x][i];
            }
        }
        return sz[x];
    }
};